package algorithms.question.class01;

import common.util.MyUtil;

/**
 * 给定一个数组arr，你可以在每个数字之前决定+或者-
 * 但是必须所有数字都参与
 * 再给定一个数target，请问最后算出target的方法数是多少？
 *
 * @author guichang
 * @date 2021/7/29
 */

@SuppressWarnings("all")
public class Code7_算出target的方法数 {

    public static void main(String[] args) {
        int[] arr = MyUtil.createArray(1, 2, 3, 4, 5, 6, 7, 8);
        MyUtil.print(ways(arr, 4));

    }

    public static int ways(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return process(arr, 0, target);
    }

    /**
     * 当前来到第i号元素，凑出rest的方法数
     */
    public static int process(int[] arr, int i, int rest) {
        if (i == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        // i号 +
        int p1 = process(arr, i + 1, rest + arr[i]);
        // i号 -
        int p2 = process(arr, i + 1, rest - arr[i]);
        return p1 + p2;
    }

}